** עצי B - ניתוח לשיעורין:

• המשפט המרכזי:
  • בעץ B המשתמש בהכנסה ומחיקה בשני מעברים (two pass), החל ממצב של עץ ריק, לכל רצף של $m$ פעולות הכנסה ומחיקה, מספר הפעולות הכולל של מיזוג, פיצול והזזה חסום ממעל ב- $\frac{3}{2}m$.
• שיטת החישוב:
  • עלות כל פעולת מיזוג, פיצול והזזה מוגדרת כ-1.
  • החיוב הנגבה עבור כל פעולת הכנסה או מחיקה הוא $\frac{3}{2}$.
• שמירה על אינווריאנטה:
  • כל צומת שאיננו השורש ויש בו $t-1$ מפתחות יאגור 0.5 מטבעות.
  • כל צומת עמוס שיש בו $2t-1$ מפתחות יאגור 1.5 מטבעות.
• ניתוח פעולת הכנסה:
  • כאשר מתבצעת הכנסה והצומת מגיע ל-$2t-1$ מפתחות, הוא יפוצל לשני צמתים בעלי $t-1$ ו-$t$ מפתחות.
  • את העלות של פעולת הפיצול (1) אנו מממנים באמצעות ה-1.5 מטבעות שנאגרו בצומת העמוס, ואת ה-0.5 מטבעות הנותרים אנו מניחים בצומת החדש שנוצר עם ה-$t-1$ מפתחות.
  • אם מספר המפתחות בצומת האב עולה ל-$2t-1$, ניקח 1.5 מטבעות מתוך החיוב המקורי ששילמנו על פעולת ההכנסה כולה ונניח אותם עליו.
• ניתוח פעולת מחיקה:
  • בפעולת מיזוג, שני צמתים עם $t-1$ מפתחות מתאחדים לצומת אחד בעל $2t-2$ מפתחות. העלות למיזוג משולמת על ידי שימוש ב-0.5 מטבעות שהיו אגורים בכל אחד מהצמתים המתמזגים.
  • אם מתבצעת פעולת הזזה (Shift), נשתמש ב-1 מטבעות מהחיוב של פעולת המחיקה כדי לשלם עליה.
  • אם לאחר מחיקה או הזזה מספר המפתחות של הצומת או של אחיו יורד בדיוק ל-$t-1$, לוקחים 0.5 מטבעות מהחיוב ומניחים עליו כדי לשמר את האינווריאנטה.

ביטול האמורטיזציה של גיבוב מחדש (Deamortization of rehashing):

• המטרה:
  • בטבלאות גיבוב , אנו שואפים לשמור על יחס תפוסה (Load factor) של $n/m\in \mathrm{\Theta }(1)$ כדי להבטיח זמן חיפוש של $\mathrm{\Theta }(1)$ תוך שימוש במקום זיכרון פרופורציונלי למידע $\mathrm{\Theta }(n)$.
  • פעולת הגיבוב מחדש (Rehashing) הרגילה מעניקה לנו זמן ריצה אמורטיזי של $\mathrm{\Theta }(1)$, אך במקרה הגרוע ביותר דורשת $\mathrm{\Theta }(n)$ בבת אחת. המטרה פה היא להראות איך אפשר להפוך את פעולת ה-Rehashing כך שתדרוש תמיד זמן של $\mathrm{\Theta }(1)$ גם במקרה הגרוע ביותר.
• אופן הפעולה (הכנסה הדרגתית):
  • אנו מנהלים ושומרים תמיד שתי טבלאות גיבוב במקביל:
    • טבלה ראשית $T$ בגודל $m$
    • טבלה חלופית $T^{\prime }$ בגודל $2m$.
  • ברגע שטבלה $T$ מגיעה בדיוק לחצי מקיבולתה ($m/2$ איברים), הטבלה החדשה $T^{\prime }$ תיווצר ותהיה ריקה.
  • בכל אחת מ-$m/2$ פעולות ההכנסה הבאות, נבצע צעדים בודדים מתוך אלגוריתם ההעתקה המלא:
    • אם האיבר החדש הוכנס אחרי סמן הסריקה הנוכחי שלנו, נבצע 4 צעדי העתקה לטבלה החדשה.
    • אחרת, נכניס אותו ישירות אל $T^{\prime }$ ונבצע 3 צעדים.
  • כאשר טבלה $T$ מתמלאת לחלוטין (מגיעה ל-$m$ איברים), כל האיברים שלה למעשה כבר הספיקו לעבור ל-$T^{\prime }$ באופן הדרגתי. בשלב זה פשוט מחליפים מצביעים ($T\leftarrow T^{\prime }$) ומייצרים טבלה חלופית חדשה $T^{\prime }$ שגודלה יהיה $4m$ (בעזרת מערך חכם).

עצי BB($\alpha$):

• הגדרות ומושגי יסוד:
  • פונקציית הגודל $size(v)$ מייצגת את מספר הקודקודים הנמצאים בתת-העץ ששורשו הוא $v$.
  • קודקוד $v$ מוגדר כבעל איזון חסום $\alpha$ אם ורק אם מתקיים: גודל תת-העץ השמאלי שלו מקיים $size(v.left)\ge \lfloor \alpha \cdot size(v)\rfloor$ וגודל תת-העץ הימני מקיים $size(v.right)\ge \lfloor \alpha \cdot size(v)\rfloor$.
  • עץ מטיפוס זה (עבור $\alpha <0.5$) הוא עץ חיפוש בינארי בו כל הצמתים מקיימים את חסם האיזון $\alpha$. במצב כזה מובטח שגובה העץ $T$ חסום על ידי ${\log }_{1/(1-\alpha )}|T|$.
• פעולות הכנסה ומחיקה (Insertion and deletion):
  • תחילה מכניסים או מוחקים איבר בדיוק כמו בעץ חיפוש בינארי רגיל.
  • בודקים אם האיזון הופר, ומוצאים את הצומת הגבוה ביותר (קרוב ביותר לשורש) שנקרא $w$ אשר חורג מחסם האיזון $\alpha$.
  • במידה וצומת כזה קיים, מחליפים את כל תת-העץ של $w$ בעץ חדש המאוזן בצורה מושלמת ומכיל את אותם איברים.
  • סיבוכיות הזמן: במקרה הגרוע ביותר לבניה מחדש זו היא $\mathrm{\Theta }(|T|)$ פרופורציונלית לגודל תת-העץ המקורי $size(w)$ פלוס גובה העץ.
• ניתוח סיבוכיות לשיעורין:
  • ניתוח של רצף $n$ הכנסות אל עץ ריק עבור המקרה $\alpha =1/3$: עלות כל פעולת הכנסה ממשית היא הגובה פלוס גודל הבניה מחדש: $(height(T)+1)+size(w)$.
  • אנו "נגבה" (Charge) על כל הכנסה מחיר מוגדל של $4(height(T)+1)$.
  • מתוך הסכום הזה נשלם מיד $height(T)+1$ על פעולת ההכנסה העדכנית ב-BST, ונפזר 3 דולרים כחיסכון עתידי בכל אחד מהצמתים הפנימיים במסלול מהשורש ועד לעלה החדש.
  • הבטחת תשלום: כאשר צומת $w$ יוצא מאיזון, נוכל להראות שמספר פעולות ההכנסה שבוצעו בו מאז האיזון הקודם שלו הוא לפחות $\frac{1}{3}size(w)$.
  • כיוון שכל אחת מהכנסות אלו הפקידה 3 דולרים אצלו, הצומת יאגור בסך הכל לפחות $3\cdot \frac{1}{3}size(w)=size(w)$ דולרים. זהו בדיוק הסכום הנדרש כדי לשלם על הבניה מחדש במקרה הגרוע.
  • סה"כ עלות אמורטיזית עבור כל צעד היא $O(\log n)$ (שכן החיוב הוא כפולת גובה העץ), ולכן עבור $n$ פעולות משלמים בתוחלת זמן של $O(n\log n)$.